package qsc.algorithm.greedyAlgorithm;

import java.util.*;

/**
 * @auther QiuShangcheng
 * @create 2021/5/2
 */
public class Review {
    public static void main(String[] args) {
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        HashSet<String> K1 = new HashSet<>();
        K1.add("北京");
        K1.add("上海");
        K1.add("天津");
        HashSet<String> K2 = new HashSet<String>();
        K2.add("广州");
        K2.add("北京");
        K2.add("深圳");
        HashSet<String> K3 = new HashSet<String>();
        K3.add("成都");
        K3.add("上海");
        K3.add("杭州");
        HashSet<String> K4 = new HashSet<String>();
        K4.add("上海");
        K4.add("天津");
        HashSet<String> K5 = new HashSet<String>();
        K5.add("杭州");
        K5.add("大连");
        broadcasts.put("K1", K1);
        broadcasts.put("K2", K2);
        broadcasts.put("K3", K3);
        broadcasts.put("K4", K4);
        broadcasts.put("K5", K5);

        HashSet<String> allAreas = new HashSet<String>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");

        System.out.println(greedyAlgorithm(broadcasts, allAreas));

    }

    public static List<String> greedyAlgorithm(HashMap<String, HashSet<String>> broadcasts, HashSet<String> allAreas) {
        ArrayList<String> selects = new ArrayList<>();
        HashSet<String> temp = new HashSet<>();
        String maxKey;
        int maxCount;
//        int curCount;
        while (allAreas.size() != 0) {
            maxCount = 0;
            maxKey = null;
            for (String key : broadcasts.keySet()
            ) {
                temp.clear();
                temp.addAll(broadcasts.get(key));
                temp.retainAll(allAreas);
                int curCount = temp.size();
                if (curCount > maxCount) {
                    maxCount = curCount;
                    maxKey = key;
                }
            }
            if (maxKey != null) {
                selects.add(maxKey);
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println("最佳的选择为：" + selects);
        return selects;
    }

}
